SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Stochastic programming</title>

</head>

Stochastic programming

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">For the context of control theory, see <a href="Stochastic_control" title="Stochastic control">Stochastic control</a>.</div>

In the field of <a href="Mathematical_optimization" title="Mathematical optimization">mathematical optimization</a>, stochastic programming is a framework for <a href="Mathematical_model" title="Mathematical model">modeling</a> <a href="Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)">optimization</a> problems that involve <a href="Uncertainty" title="Uncertainty">uncertainty</a>. A stochastic program is an optimization problem in which some or all problem parameters are uncertain, but follow known <a href="Probability_distribution" title="Probability distribution">probability distributions</a>.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a> This framework contrasts with deterministic optimization, in which all problem parameters are assumed to be known exactly. The goal of stochastic programming is to find a decision which both optimizes some criteria chosen by the decision maker, and appropriately accounts for the uncertainty of the problem parameters. Because many real-world decisions involve uncertainty, stochastic programming has found applications in a broad range of areas ranging from <a href="Finance" title="Finance">finance</a> to <a href="Transportation" class="mw-redirect" title="Transportation">transportation</a> to energy optimization.<a href="#cite_note-3">[3]</a><a href="#cite_note-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Methods">Methods</h2></div>

Several stochastic programming methods have been developed:

<ul><li>Scenario-based methods including Sample Average Approximation</li>

<li>Stochastic integer programming for problems in which some variables must be integers</li>

<li><a href="Chance_constrained_programming" title="Chance constrained programming">Chance constrained programming</a> for dealing with constraints that must be satisfied with a given probability</li>

<li><a href="Stochastic_dynamic_programming" title="Stochastic dynamic programming">Stochastic dynamic programming</a></li>

<li><a href="Markov_decision_process" title="Markov decision process">Markov decision process</a></li>

<li><a href="Benders_decomposition" title="Benders decomposition">Benders decomposition</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Two-stage_problem_definition">Two-stage problem definition</h2></div>

The basic idea of two-stage stochastic programming is that (optimal) decisions should be based on data available at the time the decisions are made and cannot depend on future observations. The two-stage formulation is widely used in stochastic programming. The general formulation of a two-stage stochastic programming problem is given by:

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{x\in X}\{g(x)=f(x)+E_{\xi }[Q(x,\xi )]\}}</annotation>

</semantics>

</math>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q(x,\xi )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q(x,\xi )}</annotation>

</semantics>

</math><img src="./beeded4b58c4411fb809b80bfbe76364e0ae7c90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.041ex; height:2.843ex;" alt="{\displaystyle Q(x,\xi )}" loading="lazy"> is the optimal value of the second-stage problem

</mrow>

</munder>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{y}\{q(y,\xi )\,|\,T(\xi )x+W(\xi )y=h(\xi )\}.}</annotation>

</semantics>

</math>

The classical two-stage linear stochastic programming problems can be formulated as

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{llr}\min \limits _{x\in \mathbb {R} ^{n}}&g(x)=c^{T}x+E_{\xi }[Q(x,\xi )]&\\{\text{subject to}}&Ax=b&\\&x\geq 0&\end{array}}}</annotation>

</semantics>

</math>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q(x,\xi )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q(x,\xi )}</annotation>

</semantics>

</math><img src="./beeded4b58c4411fb809b80bfbe76364e0ae7c90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.041ex; height:2.843ex;" alt="{\displaystyle Q(x,\xi )}" loading="lazy"> is the optimal value of the second-stage problem

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{llr}\min \limits _{y\in \mathbb {R} ^{m}}&q(\xi )^{T}y&\\{\text{subject to}}&T(\xi )x+W(\xi )y=h(\xi )&\\&y\geq 0&\end{array}}}</annotation>

</semantics>

</math>

In such formulation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \mathbb {R} ^{n}}</annotation>

</semantics>

</math><img src="./c520ee2cb6ccf8a93c89a8c58a8378796bd52e53.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.067ex; height:2.343ex;" alt="{\displaystyle x\in \mathbb {R} ^{n}}" loading="lazy"> is the first-stage decision variable vector, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in \mathbb {R} ^{m}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in \mathbb {R} ^{m}}</annotation>

</semantics>

</math><img src="./a7c75924c9d90bfb3e00336cdb864e54312e601e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.349ex; height:2.676ex;" alt="{\displaystyle y\in \mathbb {R} ^{m}}" loading="lazy"> is the second-stage decision variable vector, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi (q,T,W,h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi (q,T,W,h)}</annotation>

</semantics>

</math><img src="./7ba0415cd98433dc75dcc72176192e770743f88a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.421ex; height:2.843ex;" alt="{\displaystyle \xi (q,T,W,h)}" loading="lazy"> contains the data of the second-stage problem. In this formulation, at the first stage we have to make a "here-and-now" decision <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> before the realization of the uncertain data <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy">, viewed as a random vector, is known. At the second stage, after a realization of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy"> becomes available, we optimize our behavior by solving an appropriate optimization problem.

At the first stage we optimize (minimize in the above formulation) the cost <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c^{T}x}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c^{T}x}</annotation>

</semantics>

</math><img src="./c4b3eef5196781e2d7c4256fc30a5ab29e5c8c04.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.726ex; height:2.676ex;" alt="{\displaystyle c^{T}x}" loading="lazy"> of the first-stage decision plus the expected cost of the (optimal) second-stage decision. We can view the second-stage problem simply as an optimization problem which describes our supposedly optimal behavior when the uncertain data is revealed, or we can consider its solution as a recourse action where the term <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Wy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Wy}</annotation>

</semantics>

</math><img src="./15f6ce9256a02883662d8f513f0cf83035acb8a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.591ex; height:2.509ex;" alt="{\displaystyle Wy}" loading="lazy"> compensates for a possible inconsistency of the system <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Tx\leq h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Tx\leq h}</annotation>

</semantics>

</math><img src="./2dddcc52f7f8faf0c83f78592eefec17cab0b3ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.403ex; height:2.343ex;" alt="{\displaystyle Tx\leq h}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{T}y}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{T}y}</annotation>

</semantics>

</math><img src="./14cab7e06c673625a6d666cf80ee660c3b72964b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.624ex; height:3.009ex;" alt="{\displaystyle q^{T}y}" loading="lazy"> is the cost of this recourse action.

The considered two-stage problem is linear because the objective functions and the constraints are linear. Conceptually this is not essential and one can consider more general two-stage stochastic programs. For example, if the first-stage problem is integer, one could add integrality constraints to the first-stage problem so that the feasible set is discrete. Non-linear objectives and constraints could also be incorporated if needed.<a href="#cite_note-5">[5]</a>

<div class="mw-heading mw-heading3"><h3 id="Distributional_assumption">Distributional assumption</h3></div>

The formulation of the above two-stage problem assumes that the second-stage data <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy"> is modeled as a random vector with a known probability distribution. This would be justified in many situations. For example, the distribution of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy"> could be inferred from historical data if one assumes that the distribution does not significantly change over the considered period of time. Also, the empirical distribution of the sample could be used as an approximation to the distribution of the future values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy">. If one has a prior model for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy">, one could obtain a posteriori distribution by a Bayesian update.

<div class="mw-heading mw-heading2"><h2 id="Scenario-based_approach">Scenario-based approach</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Discretization">Discretization</h3></div>

To solve the two-stage stochastic problem numerically, one often needs to assume that the random vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy"> has a finite number of possible realizations, called scenarios, say <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{1},\dots ,\xi _{K}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{1},\dots ,\xi _{K}}</annotation>

</semantics>

</math><img src="./3368a7787acfc22821e8a811c9c11c19fea78120.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.962ex; height:2.509ex;" alt="{\displaystyle \xi _{1},\dots ,\xi _{K}}" loading="lazy">, with respective probability masses <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1},\dots ,p_{K}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1},\dots ,p_{K}}</annotation>

</semantics>

</math><img src="./3379d47432680aa7f5f1f5c25830223669cff332.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:10.354ex; height:2.009ex;" alt="{\displaystyle p_{1},\dots ,p_{K}}" loading="lazy">. Then the expectation in the first-stage problem's objective function can be written as the summation:

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E[Q(x,\xi )]=\sum \limits _{k=1}^{K}p_{k}Q(x,\xi _{k})}</annotation>

</semantics>

</math>

and, moreover, the two-stage problem can be formulated as one large linear programming problem (this is called the deterministic equivalent of the original problem, see section <a href="#Deterministic_equivalent_of_a_stochastic_problem">§ Deterministic equivalent of a stochastic problem</a>).

When <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy"> has an infinite (or very large) number of possible realizations the standard approach is then to represent this distribution by scenarios. This approach raises three questions, namely:

<ol><li>How to construct scenarios, see <a href="#Scenario_construction">§ Scenario construction</a>;</li>

<li>How to solve the deterministic equivalent. Optimizers such as <a href="CPLEX" title="CPLEX">CPLEX</a>, and <a href="GNU_Linear_Programming_Kit" title="GNU Linear Programming Kit">GLPK</a> can solve large linear/nonlinear problems. The NEOS Server,<a href="#cite_note-neos-6">[6]</a> hosted at the <a href="University_of_Wisconsin%2C_Madison" class="mw-redirect" title="University of Wisconsin, Madison">University of Wisconsin, Madison</a>, allows free access to many modern solvers. The structure of a deterministic equivalent is particularly amenable to apply decomposition methods,<a href="#cite_note-7">[7]</a> such as <a href="Benders'_decomposition" class="mw-redirect" title="Benders' decomposition">Benders' decomposition</a> or scenario decomposition;</li>

<li>How to measure quality of the obtained solution with respect to the "true" optimum.</li></ol>

These questions are not independent. For example, the number of scenarios constructed will affect both the tractability of the deterministic equivalent and the quality of the obtained solutions.

<div class="mw-heading mw-heading3"><h3 id="Stochastic_linear_programming">Stochastic linear programming</h3></div>

A stochastic <a href="Linear_program" class="mw-redirect" title="Linear program">linear program</a> is a specific instance of the classical two-stage stochastic program. A stochastic LP is built from a collection of multi-period linear programs (LPs), each having the same structure but somewhat different data. The <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k^{th}}</annotation>

</semantics>

</math><img src="./c348e1c6f8200f15d1d6026fc140d554b272096d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.984ex; height:2.676ex;" alt="{\displaystyle k^{th}}" loading="lazy"> two-period LP, representing the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k^{th}}</annotation>

</semantics>

</math><img src="./c348e1c6f8200f15d1d6026fc140d554b272096d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.984ex; height:2.676ex;" alt="{\displaystyle k^{th}}" loading="lazy"> scenario, may be regarded as having the following form:

<mtr>

<mtd>

<mtext>Minimize</mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lccccccc}{\text{Minimize}}&f^{T}x&+&g^{T}y&+&h_{k}^{T}z_{k}&&\\{\text{subject to}}&Tx&+&Uy&&&=&r\\&&&V_{k}y&+&W_{k}z_{k}&=&s_{k}\\&x&,&y&,&z_{k}&\geq &0\end{array}}}</annotation>

</semantics>

</math><img src="./46766aa3c29f1e4e9e0b8ae56245dbe820ae7772.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.005ex; width:47.598ex; height:13.176ex;" alt="{\displaystyle {\begin{array}{lccccccc}{\text{Minimize}}&f^{T}x&+&g^{T}y&+&h_{k}^{T}z_{k}&&\\{\text{subject to}}&Tx&+&Uy&&&=&r\\&&&V_{k}y&+&W_{k}z_{k}&=&s_{k}\\&x&,&y&,&z_{k}&\geq &0\end{array}}}" loading="lazy">

The vectors <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> contain the first-period variables, whose values must be chosen immediately. The vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{k}}</annotation>

</semantics>

</math><img src="./a51cdfac24f8b95ed711f11ea9502da4087b6a24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.17ex; height:2.009ex;" alt="{\displaystyle z_{k}}" loading="lazy"> contains all of the variables for subsequent periods. The constraints <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Tx+Uy=r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Tx+Uy=r}</annotation>

</semantics>

</math><img src="./f9adf9096020cdf3be7f17b2b7a29966100acd8c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.892ex; height:2.509ex;" alt="{\displaystyle Tx+Uy=r}" loading="lazy"> involve only first-period variables and are the same in every scenario. The other constraints involve variables of later periods and differ in some respects from scenario to scenario, reflecting uncertainty about the future.

Note that solving the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k^{th}}</annotation>

</semantics>

</math><img src="./c348e1c6f8200f15d1d6026fc140d554b272096d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.984ex; height:2.676ex;" alt="{\displaystyle k^{th}}" loading="lazy"> two-period LP is equivalent to assuming the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k^{th}}</annotation>

</semantics>

</math><img src="./c348e1c6f8200f15d1d6026fc140d554b272096d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.984ex; height:2.676ex;" alt="{\displaystyle k^{th}}" loading="lazy"> scenario in the second period with no uncertainty. In order to incorporate uncertainties in the second stage, one should assign probabilities to different scenarios and solve the corresponding deterministic equivalent.

<div class="mw-heading mw-heading4"><h4 id="Deterministic_equivalent_of_a_stochastic_problem">Deterministic equivalent of a stochastic problem</h4></div>

With a finite number of scenarios, two-stage stochastic linear programs can be modelled as large linear programming problems. This formulation is often called the deterministic equivalent linear program, or abbreviated to deterministic equivalent. (Strictly speaking a deterministic equivalent is any mathematical program that can be used to compute the optimal first-stage decision, so these will exist for continuous probability distributions as well, when one can represent the second-stage cost in some closed form.)

For example, to form the deterministic equivalent to the above stochastic linear program, we assign a probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{k}}</annotation>

</semantics>

</math><img src="./01084a31964201514f3e6bd0136989e11ea6e58a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.348ex; height:2.009ex;" alt="{\displaystyle p_{k}}" loading="lazy"> to each scenario <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=1,\dots ,K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=1,\dots ,K}</annotation>

</semantics>

</math><img src="./818ab978c8de06a8d46ee43572d2e20e41305189.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.716ex; height:2.509ex;" alt="{\displaystyle k=1,\dots ,K}" loading="lazy">. Then we can minimize the expected value of the objective, subject to the constraints from all scenarios:

<mtr>

<mtd>

<mtext>Minimize</mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lccccccccccccc}{\text{Minimize}}&f^{\top }x&+&g^{\top }y&+&p_{1}h_{1}^{\top }z_{1}&+&p_{2}h_{2}^{T}z_{2}&+&\cdots &+&p_{K}h_{K}^{\top }z_{K}&&\\{\text{subject to}}&Tx&+&Uy&&&&&&&&&=&r\\&&&V_{1}y&+&W_{1}z_{1}&&&&&&&=&s_{1}\\&&&V_{2}y&&&+&W_{2}z_{2}&&&&&=&s_{2}\\&&&\vdots &&&&&&\ddots &&&&\vdots \\&&&V_{K}y&&&&&&&+&W_{K}z_{K}&=&s_{K}\\&x&,&y&,&z_{1}&,&z_{2}&,&\ldots &,&z_{K}&\geq &0\\\end{array}}}</annotation>

</semantics>

</math><img src="./663adb2ad68d23e28dfa849ec6069758230b265c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -11.671ex; width:88.716ex; height:24.509ex;" alt="{\displaystyle {\begin{array}{lccccccccccccc}{\text{Minimize}}&f^{\top }x&+&g^{\top }y&+&p_{1}h_{1}^{\top }z_{1}&+&p_{2}h_{2}^{T}z_{2}&+&\cdots &+&p_{K}h_{K}^{\top }z_{K}&&\\{\text{subject to}}&Tx&+&Uy&&&&&&&&&=&r\\&&&V_{1}y&+&W_{1}z_{1}&&&&&&&=&s_{1}\\&&&V_{2}y&&&+&W_{2}z_{2}&&&&&=&s_{2}\\&&&\vdots &&&&&&\ddots &&&&\vdots \\&&&V_{K}y&&&&&&&+&W_{K}z_{K}&=&s_{K}\\&x&,&y&,&z_{1}&,&z_{2}&,&\ldots &,&z_{K}&\geq &0\\\end{array}}}" loading="lazy">

We have a different vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{k}}</annotation>

</semantics>

</math><img src="./a51cdfac24f8b95ed711f11ea9502da4087b6a24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.17ex; height:2.009ex;" alt="{\displaystyle z_{k}}" loading="lazy"> of later-period variables for each scenario <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">. The first-period variables <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> are the same in every scenario, however, because we must make a decision for the first period before we know which scenario will be realized. As a result, the constraints involving just <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> need only be specified once, while the remaining constraints must be given separately for each scenario.

<div class="mw-heading mw-heading3"><h3 id="Scenario_construction">Scenario construction</h3></div>

In practice it might be possible to construct scenarios by eliciting experts' opinions on the future. The number of constructed scenarios should be relatively modest so that the obtained deterministic equivalent can be solved with reasonable computational effort. It is often claimed that a solution that is optimal using only a few scenarios provides more adaptable plans than one that assumes a single scenario only. In some cases such a claim could be verified by a simulation. In theory some measures of guarantee that an obtained solution solves the original problem with reasonable accuracy. Typically in applications only the first stage optimal solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math><img src="./e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"> has a practical value since almost always a "true" realization of the random data will be different from the set of constructed (generated) scenarios.

Suppose <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy"> contains <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> independent random components, each of which has three possible realizations (for example, future realizations of each random parameters are classified as low, medium and high), then the total number of scenarios is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K=3^{d}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K=3^{d}}</annotation>

</semantics>

</math><img src="./277b6548aaea7ee1b3afc67615fcc78eb1653a8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.419ex; height:2.676ex;" alt="{\displaystyle K=3^{d}}" loading="lazy">. Such exponential growth of the number of scenarios makes model development using expert opinion very difficult even for reasonable size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy">. The situation becomes even worse if some random components of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy"> have continuous distributions.

<div class="mw-heading mw-heading4"><h4 id="Monte_Carlo_sampling_and_Sample_Average_Approximation_(SAA)_Method">Monte Carlo sampling and Sample Average Approximation (SAA) Method</h4></div>

A common approach to reduce the scenario set to a manageable size is by using Monte Carlo simulation. Suppose the total number of scenarios is very large or even infinite. Suppose further that we can generate a sample <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}</annotation>

</semantics>

</math><img src="./18e337666a1acdcff1926a468ca5fb4f210ec363.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.113ex; height:3.009ex;" alt="{\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> realizations of the random vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy">. Usually the sample is assumed to be <a href="Independent_and_identically_distributed" class="mw-redirect" title="Independent and identically distributed">independent and identically distributed</a> (i.i.d sample). Given a sample, the expectation function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q(x)=E[Q(x,\xi )]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(x)=E[Q(x,\xi )]}</annotation>

</semantics>

</math><img src="./3b800a7fbfbddea6252c4c00a7170d77aa6d1746.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.418ex; height:2.843ex;" alt="{\displaystyle q(x)=E[Q(x,\xi )]}" loading="lazy"> is approximated by the sample average

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {q}}_{N}(x)={\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}</annotation>

</semantics>

</math><img src="./733e629bb214830fbaf8a54cecfea0b2a8d2947d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:24.29ex; height:7.676ex;" alt="{\displaystyle {\hat {q}}_{N}(x)={\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}" loading="lazy">

and consequently the first-stage problem is given by

<mtr>

<mtd>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{rlrrr}{\hat {g}}_{N}(x)=&\min \limits _{x\in \mathbb {R} ^{n}}&c^{T}x+{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})&\\&{\text{subject to}}&Ax&=&b\\&&x&\geq &0\end{array}}}</annotation>

</semantics>

</math><img src="./39d98ab0618dce1b3b2e44f801dbca5bd0e5f627.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.005ex; width:54.413ex; height:11.176ex;" alt="{\displaystyle {\begin{array}{rlrrr}{\hat {g}}_{N}(x)=&\min \limits _{x\in \mathbb {R} ^{n}}&c^{T}x+{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})&\\&{\text{subject to}}&Ax&=&b\\&&x&\geq &0\end{array}}}" loading="lazy">

This formulation is known as the Sample Average Approximation method. The SAA problem is a function of the considered sample and in that sense is random. For a given sample <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}</annotation>

</semantics>

</math><img src="./18e337666a1acdcff1926a468ca5fb4f210ec363.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.113ex; height:3.009ex;" alt="{\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}" loading="lazy"> the SAA problem is of the same form as a two-stage stochastic linear programming problem with the scenarios <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi ^{j}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi ^{j}}</annotation>

</semantics>

</math><img src="./3e8c1e8b84bee1edf89af78cad3a1ade2c2b613c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.943ex; height:3.009ex;" alt="{\displaystyle \xi ^{j}}" loading="lazy">., <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=1,\dots ,N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=1,\dots ,N}</annotation>

</semantics>

</math><img src="./4d46286d33a5b753666549eef55a5c423f9e3e30.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:12.488ex; height:2.509ex;" alt="{\displaystyle j=1,\dots ,N}" loading="lazy">, each taken with the same probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{j}={\frac {1}{N}}}">

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{j}={\frac {1}{N}}}</annotation>

</semantics>

</math><img src="./e66dd95278b88b868b94e6918eeb1aa7759bd6b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; margin-left: -0.089ex; width:8.167ex; height:5.176ex;" alt="{\displaystyle p_{j}={\frac {1}{N}}}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Statistical_inference">Statistical inference</h3></div>

Consider the following stochastic programming problem

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min \limits _{x\in X}\{g(x)=f(x)+E[Q(x,\xi )]\}}</annotation>

</semantics>

</math><img src="./161c2b7f54a3e783d3b8edc45b2ab66a62fc4671.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:30.922ex; height:4.009ex;" alt="{\displaystyle \min \limits _{x\in X}\{g(x)=f(x)+E[Q(x,\xi )]\}}" loading="lazy"></div>

Here <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> is a nonempty closed subset of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{n}}</annotation>

</semantics>

</math><img src="./c510b63578322050121fe966f2e5770bea43308d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.897ex; height:2.343ex;" alt="{\displaystyle \mathbb {R} ^{n}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy"> is a random vector whose probability distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> is supported on a set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Xi \subset \mathbb {R} ^{d}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Xi \subset \mathbb {R} ^{d}}</annotation>

</semantics>

</math><img src="./d84b38938650149b1a8263e589b66e3dfe3fb705.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.419ex; height:2.676ex;" alt="{\displaystyle \Xi \subset \mathbb {R} ^{d}}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q:X\times \Xi \rightarrow \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q:X\times \Xi \rightarrow \mathbb {R} }</annotation>

</semantics>

</math><img src="./aae38636516412c0758de246023f5d4e9080dba7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.438ex; height:2.509ex;" alt="{\displaystyle Q:X\times \Xi \rightarrow \mathbb {R} }" loading="lazy">. In the framework of two-stage stochastic programming, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q(x,\xi )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q(x,\xi )}</annotation>

</semantics>

</math><img src="./beeded4b58c4411fb809b80bfbe76364e0ae7c90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.041ex; height:2.843ex;" alt="{\displaystyle Q(x,\xi )}" loading="lazy"> is given by the optimal value of the corresponding second-stage problem.

Assume that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math><img src="./c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy"> is well defined and finite valued for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation>

</semantics>

</math><img src="./3e580967f68f36743e894aa7944f032dda6ea01d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}" loading="lazy">. This implies that for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation>

</semantics>

</math><img src="./3e580967f68f36743e894aa7944f032dda6ea01d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}" loading="lazy"> the value <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q(x,\xi )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q(x,\xi )}</annotation>

</semantics>

</math><img src="./beeded4b58c4411fb809b80bfbe76364e0ae7c90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.041ex; height:2.843ex;" alt="{\displaystyle Q(x,\xi )}" loading="lazy"> is finite almost surely.

Suppose that we have a sample <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi ^{1},\dots ,\xi ^{N}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi ^{1},\dots ,\xi ^{N}}</annotation>

</semantics>

</math><img src="./bd415b124eae07051e74137c87476d8add34ada7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.991ex; height:3.009ex;" alt="{\displaystyle \xi ^{1},\dots ,\xi ^{N}}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">realizations of the random vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy">. This random sample can be viewed as historical data of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> observations of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi }</annotation>

</semantics>

</math><img src="./e0b461aaf61091abd5d2c808931c48b8ff9647db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.03ex; height:2.509ex;" alt="{\displaystyle \xi }" loading="lazy">, or it can be generated by Monte Carlo sampling techniques. Then we can formulate a corresponding sample average approximation

</mrow>

</munder>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min \limits _{x\in X}\{{\hat {g}}_{N}(x)=f(x)+{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})\}}</annotation>

</semantics>

</math><img src="./8c09c685b7aee11b8942cfb8630b913dfcac15e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:37.602ex; height:7.676ex;" alt="{\displaystyle \min \limits _{x\in X}\{{\hat {g}}_{N}(x)=f(x)+{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})\}}" loading="lazy"></div>

By the <a href="Law_of_large_numbers" title="Law of large numbers">law of large numbers</a> we have that, under some regularity conditions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}">

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}</annotation>

</semantics>

</math><img src="./1169b9bcb070fa01687a57bb5b22a959bd21746b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:14.984ex; height:7.676ex;" alt="{\displaystyle {\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}" loading="lazy"> converges pointwise with probability 1 to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E[Q(x,\xi )]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E[Q(x,\xi )]}</annotation>

</semantics>

</math><img src="./8de948ea64600cb9e6bb7c1b536f5a74813719b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.111ex; height:2.843ex;" alt="{\displaystyle E[Q(x,\xi )]}" loading="lazy"> as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\rightarrow \infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\rightarrow \infty }</annotation>

</semantics>

</math><img src="./3c6337428441dbe11ca917f0d9115e8cf3a78f40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.001ex; height:2.176ex;" alt="{\displaystyle N\rightarrow \infty }" loading="lazy">. Moreover, under mild additional conditions the convergence is uniform. We also have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E[{\hat {g}}_{N}(x)]=g(x)}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E[{\hat {g}}_{N}(x)]=g(x)}</annotation>

</semantics>

</math><img src="./20be6eddd812ab84d9689fe9f2797bf6d625b9e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.485ex; height:2.843ex;" alt="{\displaystyle E[{\hat {g}}_{N}(x)]=g(x)}" loading="lazy">, i.e., <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {g}}_{N}(x)}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {g}}_{N}(x)}</annotation>

</semantics>

</math><img src="./97feeb8799bbd8d617d164ca640abe67ca9fa22b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.062ex; height:2.843ex;" alt="{\displaystyle {\hat {g}}_{N}(x)}" loading="lazy"> is an unbiased estimator of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math><img src="./c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy">. Therefore, it is natural to expect that the optimal value and optimal solutions of the SAA problem converge to their counterparts of the true problem as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\rightarrow \infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\rightarrow \infty }</annotation>

</semantics>

</math><img src="./3c6337428441dbe11ca917f0d9115e8cf3a78f40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.001ex; height:2.176ex;" alt="{\displaystyle N\rightarrow \infty }" loading="lazy">.

<div class="mw-heading mw-heading4"><h4 id="Consistency_of_SAA_estimators">Consistency of SAA estimators</h4></div>

Suppose the feasible set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> of the SAA problem is fixed, i.e., it is independent of the sample. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \vartheta ^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vartheta ^{*}}</annotation>

</semantics>

</math><img src="./2ccf3c23b0c3b50c9582cf82167b12c347b2a2df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.428ex; height:2.343ex;" alt="{\displaystyle \vartheta ^{*}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S^{*}}</annotation>

</semantics>

</math><img src="./b059338b0f6bc81c4edf97c51ce987e98f4bf23e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.576ex; height:2.343ex;" alt="{\displaystyle S^{*}}" loading="lazy"> be the optimal value and the set of optimal solutions, respectively, of the true problem and let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {\vartheta }}_{N}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\vartheta }}_{N}}</annotation>

</semantics>

</math><img src="./f14f86f3b34d43586d36b47ae4df11e22b174f51.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.153ex; height:3.176ex;" alt="{\displaystyle {\hat {\vartheta }}_{N}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {S}}_{N}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {S}}_{N}}</annotation>

</semantics>

</math><img src="./6be5544c34cf923d9fdbcdf358194c6fb86274d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.264ex; height:3.176ex;" alt="{\displaystyle {\hat {S}}_{N}}" loading="lazy"> be the optimal value and the set of optimal solutions, respectively, of the SAA problem.

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g:X\rightarrow \mathbb {R} }</annotation>

</semantics>

</math><img src="./bec632524cbafa03d89c58c02227af2df3c23b45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.325ex; height:2.509ex;" alt="{\displaystyle g:X\rightarrow \mathbb {R} }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {g}}_{N}:X\rightarrow \mathbb {R} }">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {g}}_{N}:X\rightarrow \mathbb {R} }</annotation>

</semantics>

</math><img src="./a98a2fa94ac332cb09c9efe512615741633cef92.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.132ex; height:2.676ex;" alt="{\displaystyle {\hat {g}}_{N}:X\rightarrow \mathbb {R} }" loading="lazy"> be a sequence of (deterministic) real valued functions. The following two properties are equivalent:

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\overline {x}}\in X}</annotation>

</semantics>

</math><img src="./6a16bb047cdd2b0a2e75a2a795134c02b8845dce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.265ex; height:2.343ex;" alt="{\displaystyle {\overline {x}}\in X}" loading="lazy"> and any sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{x_{N}\}\subset X}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{x_{N}\}\subset X}</annotation>

</semantics>

</math><img src="./5e6d9d9d6358412744368aa439ed3d7342f8f896.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.425ex; height:2.843ex;" alt="{\displaystyle \{x_{N}\}\subset X}" loading="lazy"> converging to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\overline {x}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\overline {x}}}</annotation>

</semantics>

</math><img src="./9fa4039bbc2a0048c3a3c02e5fd24390cab0dc97.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.445ex; height:2.343ex;" alt="{\displaystyle {\overline {x}}}" loading="lazy"> it follows that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {g}}_{N}(x_{N})}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {g}}_{N}(x_{N})}</annotation>

</semantics>

</math><img src="./2e2fcfac9ab145a4c80ec9f7b4e716ca4f60e269.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.754ex; height:2.843ex;" alt="{\displaystyle {\hat {g}}_{N}(x_{N})}" loading="lazy"> converges to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g({\overline {x}})}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g({\overline {x}})}</annotation>

</semantics>

</math><img src="./8896a6552d582aa5f558a5efa00dd5bd879ae68c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.37ex; height:2.843ex;" alt="{\displaystyle g({\overline {x}})}" loading="lazy"></li>

<li>the function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(\cdot )}</annotation>

</semantics>

</math><img src="./421d5ab89ea154ac75586bdfb687db2160d1ea33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.572ex; height:2.843ex;" alt="{\displaystyle g(\cdot )}" loading="lazy"> is continuous on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {g}}_{N}(\cdot )}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {g}}_{N}(\cdot )}</annotation>

</semantics>

</math><img src="./43cd0f7751497867e2a5b1646b8b6bba2e5545e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.379ex; height:2.843ex;" alt="{\displaystyle {\hat {g}}_{N}(\cdot )}" loading="lazy"> converges to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(\cdot )}</annotation>

</semantics>

</math><img src="./421d5ab89ea154ac75586bdfb687db2160d1ea33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.572ex; height:2.843ex;" alt="{\displaystyle g(\cdot )}" loading="lazy"> uniformly on any compact subset of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></li></ul></li>

<li>If the objective of the SAA problem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {g}}_{N}(x)}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {g}}_{N}(x)}</annotation>

</semantics>

</math><img src="./97feeb8799bbd8d617d164ca640abe67ca9fa22b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.062ex; height:2.843ex;" alt="{\displaystyle {\hat {g}}_{N}(x)}" loading="lazy"> converges to the true problem's objective <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math><img src="./c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy"> with probability 1, as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\rightarrow \infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\rightarrow \infty }</annotation>

</semantics>

</math><img src="./3c6337428441dbe11ca917f0d9115e8cf3a78f40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.001ex; height:2.176ex;" alt="{\displaystyle N\rightarrow \infty }" loading="lazy">, uniformly on the feasible set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">. Then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {\vartheta }}_{N}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\vartheta }}_{N}}</annotation>

</semantics>

</math><img src="./f14f86f3b34d43586d36b47ae4df11e22b174f51.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.153ex; height:3.176ex;" alt="{\displaystyle {\hat {\vartheta }}_{N}}" loading="lazy"> converges to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \vartheta ^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vartheta ^{*}}</annotation>

</semantics>

</math><img src="./2ccf3c23b0c3b50c9582cf82167b12c347b2a2df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.428ex; height:2.343ex;" alt="{\displaystyle \vartheta ^{*}}" loading="lazy"> with probability 1 as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\rightarrow \infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\rightarrow \infty }</annotation>

</semantics>

</math><img src="./3c6337428441dbe11ca917f0d9115e8cf3a78f40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.001ex; height:2.176ex;" alt="{\displaystyle N\rightarrow \infty }" loading="lazy">.</li>

<li>Suppose that there exists a compact set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\subset \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\subset \mathbb {R} ^{n}}</annotation>

</semantics>

</math><img src="./60a7a366ba3cc8f60d9d97fccbca4ff7e00edaba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.761ex; height:2.343ex;" alt="{\displaystyle C\subset \mathbb {R} ^{n}}" loading="lazy"> such that

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> of optimal solutions of the true problem is nonempty and is contained in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></li>

<li>the function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math><img src="./c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy"> is finite valued and continuous on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></li>

<li>the sequence of functions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {g}}_{N}(x)}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {g}}_{N}(x)}</annotation>

</semantics>

</math><img src="./97feeb8799bbd8d617d164ca640abe67ca9fa22b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.062ex; height:2.843ex;" alt="{\displaystyle {\hat {g}}_{N}(x)}" loading="lazy"> converges to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math><img src="./c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy"> with probability 1, as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\rightarrow \infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\rightarrow \infty }</annotation>

</semantics>

</math><img src="./3c6337428441dbe11ca917f0d9115e8cf3a78f40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.001ex; height:2.176ex;" alt="{\displaystyle N\rightarrow \infty }" loading="lazy">, uniformly in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in C}</annotation>

</semantics>

</math><img src="./f7fc788379bff7289bdf694ffd68ee690e999eb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.937ex; height:2.176ex;" alt="{\displaystyle x\in C}" loading="lazy"></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> large enough the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {S}}_{N}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {S}}_{N}}</annotation>

</semantics>

</math><img src="./6be5544c34cf923d9fdbcdf358194c6fb86274d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.264ex; height:3.176ex;" alt="{\displaystyle {\hat {S}}_{N}}" loading="lazy"> is nonempty and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {S}}_{N}\subset C}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {S}}_{N}\subset C}</annotation>

</semantics>

</math><img src="./1c571bb4d278bdb75f7dbc17c0d5934eb3c46f93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.129ex; height:3.176ex;" alt="{\displaystyle {\hat {S}}_{N}\subset C}" loading="lazy"> with probability 1</li></ul></li></ol>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}}</annotation>

</semantics>

</math><img src="./c50df0c1d808039428a701c0e6a35dd29eafef75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.195ex; height:3.176ex;" alt="{\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}">

</mrow>

<msup>

</mrow>

</msup>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}</annotation>

</semantics>

</math><img src="./eae43fc74351cd4052ed0587d6393377b7de8897.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.138ex; height:3.343ex;" alt="{\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}" loading="lazy"> with probability 1 as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\rightarrow \infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\rightarrow \infty }</annotation>

</semantics>

</math><img src="./3c6337428441dbe11ca917f0d9115e8cf3a78f40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.001ex; height:2.176ex;" alt="{\displaystyle N\rightarrow \infty }" loading="lazy">. Note that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {D} (A,B)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {D} (A,B)}</annotation>

</semantics>

</math><img src="./be9e21f570b6e677a1dd0a21cfc146e63888346d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.028ex; height:2.843ex;" alt="{\displaystyle \mathbb {D} (A,B)}" loading="lazy"> denotes the deviation of set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> from set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy">, defined as</dd></dl></dd></dl>

</mrow>

</mrow>

</munder>

<msup>

</msup>

</mrow>

</munder>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {D} (A,B):=\sup _{x\in A}\{\inf _{x'\in B}\|x-x'\|\}}</annotation>

</semantics>

</math><img src="./fd8dc4b486f50dd20a958fc1da8f8d74e00fdc91.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:30.312ex; height:4.676ex;" alt="{\displaystyle \mathbb {D} (A,B):=\sup _{x\in A}\{\inf _{x'\in B}\|x-x'\|\}}" loading="lazy"></div>

In some situations the feasible set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> of the SAA problem is estimated, then the corresponding SAA problem takes the form

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{x\in X_{N}}{\hat {g}}_{N}(x)}</annotation>

</semantics>

</math><img src="./5d345832fbac9e8e25a729c62e33ba75e5dd59fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:11.195ex; height:4.343ex;" alt="{\displaystyle \min _{x\in X_{N}}{\hat {g}}_{N}(x)}" loading="lazy"></div>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{N}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{N}}</annotation>

</semantics>

</math><img src="./90b8110b9148fb2ec3c86f96e3b72bf2b095ce81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.616ex; height:2.509ex;" alt="{\displaystyle X_{N}}" loading="lazy"> is a subset of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{n}}</annotation>

</semantics>

</math><img src="./c510b63578322050121fe966f2e5770bea43308d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.897ex; height:2.343ex;" alt="{\displaystyle \mathbb {R} ^{n}}" loading="lazy"> depending on the sample and therefore is random. Nevertheless, consistency results for SAA estimators can still be derived under some additional assumptions:

<ol><li>Suppose that there exists a compact set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\subset \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\subset \mathbb {R} ^{n}}</annotation>

</semantics>

</math><img src="./60a7a366ba3cc8f60d9d97fccbca4ff7e00edaba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.761ex; height:2.343ex;" alt="{\displaystyle C\subset \mathbb {R} ^{n}}" loading="lazy"> such that

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> of optimal solutions of the true problem is nonempty and is contained in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></li>

<li>the function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math><img src="./c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy"> is finite valued and continuous on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></li>

<li>the sequence of functions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {g}}_{N}(x)}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {g}}_{N}(x)}</annotation>

</semantics>

</math><img src="./97feeb8799bbd8d617d164ca640abe67ca9fa22b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.062ex; height:2.843ex;" alt="{\displaystyle {\hat {g}}_{N}(x)}" loading="lazy"> converges to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math><img src="./c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy"> with probability 1, as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\rightarrow \infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\rightarrow \infty }</annotation>

</semantics>

</math><img src="./3c6337428441dbe11ca917f0d9115e8cf3a78f40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.001ex; height:2.176ex;" alt="{\displaystyle N\rightarrow \infty }" loading="lazy">, uniformly in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in C}</annotation>

</semantics>

</math><img src="./f7fc788379bff7289bdf694ffd68ee690e999eb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.937ex; height:2.176ex;" alt="{\displaystyle x\in C}" loading="lazy"></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> large enough the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {S}}_{N}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {S}}_{N}}</annotation>

</semantics>

</math><img src="./6be5544c34cf923d9fdbcdf358194c6fb86274d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.264ex; height:3.176ex;" alt="{\displaystyle {\hat {S}}_{N}}" loading="lazy"> is nonempty and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {S}}_{N}\subset C}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {S}}_{N}\subset C}</annotation>

</semantics>

</math><img src="./1c571bb4d278bdb75f7dbc17c0d5934eb3c46f93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.129ex; height:3.176ex;" alt="{\displaystyle {\hat {S}}_{N}\subset C}" loading="lazy"> with probability 1</li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{N}\in X_{N}}</annotation>

</semantics>

</math><img src="./5f03c3daebfde838890f1674b0150b83e4a2d87a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.478ex; height:2.509ex;" alt="{\displaystyle x_{N}\in X_{N}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{N}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{N}}</annotation>

</semantics>

</math><img src="./03fe4fcca886b79103468f2dbef6a0c8332b746d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.021ex; height:2.009ex;" alt="{\displaystyle x_{N}}" loading="lazy"> converges with probability 1 to a point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation>

</semantics>

</math><img src="./3e580967f68f36743e894aa7944f032dda6ea01d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}" loading="lazy"></li>

<li>for some point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in S^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in S^{*}}</annotation>

</semantics>

</math><img src="./b0e9b34582f4b7a6ba3421536c7ca73b5f5219bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.746ex; height:2.343ex;" alt="{\displaystyle x\in S^{*}}" loading="lazy"> there exists a sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{N}\in X_{N}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{N}\in X_{N}}</annotation>

</semantics>

</math><img src="./5f03c3daebfde838890f1674b0150b83e4a2d87a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.478ex; height:2.509ex;" alt="{\displaystyle x_{N}\in X_{N}}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{N}\rightarrow x}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{N}\rightarrow x}</annotation>

</semantics>

</math><img src="./5eea614f46e46a4cd9afd96124a10f9566377fdc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.965ex; height:2.176ex;" alt="{\displaystyle x_{N}\rightarrow x}" loading="lazy"> with probability 1.</li></ul></li></ol>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}}</annotation>

</semantics>

</math><img src="./c50df0c1d808039428a701c0e6a35dd29eafef75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.195ex; height:3.176ex;" alt="{\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}">

</mrow>

<msup>

</mrow>

</msup>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}</annotation>

</semantics>

</math><img src="./eae43fc74351cd4052ed0587d6393377b7de8897.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.138ex; height:3.343ex;" alt="{\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}" loading="lazy"> with probability 1 as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\rightarrow \infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\rightarrow \infty }</annotation>

</semantics>

</math><img src="./3c6337428441dbe11ca917f0d9115e8cf3a78f40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.001ex; height:2.176ex;" alt="{\displaystyle N\rightarrow \infty }" loading="lazy">.</dd></dl></dd></dl>

<div class="mw-heading mw-heading4"><h4 id="Asymptotics_of_the_SAA_optimal_value">Asymptotics of the SAA optimal value</h4></div>

Suppose the sample <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi ^{1},\dots ,\xi ^{N}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi ^{1},\dots ,\xi ^{N}}</annotation>

</semantics>

</math><img src="./bd415b124eae07051e74137c87476d8add34ada7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.991ex; height:3.009ex;" alt="{\displaystyle \xi ^{1},\dots ,\xi ^{N}}" loading="lazy"> is i.i.d. and fix a point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation>

</semantics>

</math><img src="./3e580967f68f36743e894aa7944f032dda6ea01d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}" loading="lazy">. Then the sample average estimator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {g}}_{N}(x)}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {g}}_{N}(x)}</annotation>

</semantics>

</math><img src="./97feeb8799bbd8d617d164ca640abe67ca9fa22b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.062ex; height:2.843ex;" alt="{\displaystyle {\hat {g}}_{N}(x)}" loading="lazy">, of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math><img src="./c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy">, is unbiased and has variance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{N}}\sigma ^{2}(x)}">

<mfrac>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{N}}\sigma ^{2}(x)}</annotation>

</semantics>

</math><img src="./4b28b81ec7b90f324d949635de8f2b050fdf7855.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:8.423ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{N}}\sigma ^{2}(x)}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma ^{2}(x):=Var[Q(x,\xi )]}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma ^{2}(x):=Var[Q(x,\xi )]}</annotation>

</semantics>

</math><img src="./5f306057a735880a5f769821dd74c4266aa3dafd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.67ex; height:3.176ex;" alt="{\displaystyle \sigma ^{2}(x):=Var[Q(x,\xi )]}" loading="lazy"> is supposed to be finite. Moreover, by the <a href="Central_limit_theorem" title="Central limit theorem">central limit theorem</a> we have that

<msqrt>

</msqrt>

</mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mrow>

</mpadded>

</mover>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {N}}[{\hat {g}}_{N}-g(x)]{\xrightarrow {\mathcal {D}}}Y_{x}}</annotation>

</semantics>

</math><img src="./d1a4d7c91c6049a45acde5a55fce8d68a308a659.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-top: -0.329ex; width:20.425ex; height:4.176ex;" alt="{\displaystyle {\sqrt {N}}[{\hat {g}}_{N}-g(x)]{\xrightarrow {\mathcal {D}}}Y_{x}}" loading="lazy"></div>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\xrightarrow {\mathcal {D}}}}">

<mover>

</mrow>

</mpadded>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\xrightarrow {\mathcal {D}}}}</annotation>

</semantics>

</math><img src="./550b95a7ecacfc786a776ebbd2cd7137ca9d218e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.028ex; margin-top: -0.329ex; margin-bottom: -0.477ex; width:2.591ex; height:3.843ex;" alt="{\displaystyle {\xrightarrow {\mathcal {D}}}}" loading="lazy"> denotes convergence in distribution and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y_{x}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y_{x}}</annotation>

</semantics>

</math><img src="./337e50d42108b65e30138b956c6ee377bc1e3881.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.523ex; height:2.509ex;" alt="{\displaystyle Y_{x}}" loading="lazy"> has a normal distribution with mean <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> and variance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma ^{2}(x)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma ^{2}(x)}</annotation>

</semantics>

</math><img src="./563e81ed7c5ede55b3d8844ea9bc881ec7ad0aa1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.524ex; height:3.176ex;" alt="{\displaystyle \sigma ^{2}(x)}" loading="lazy">, written as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {N}}(0,\sigma ^{2}(x))}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {N}}(0,\sigma ^{2}(x))}</annotation>

</semantics>

</math><img src="./305c4ccd55c49e14808d93fd629aa225396addf0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.062ex; width:11.866ex; height:3.176ex;" alt="{\displaystyle {\mathcal {N}}(0,\sigma ^{2}(x))}" loading="lazy">.

In other words, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {g}}_{N}(x)}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {g}}_{N}(x)}</annotation>

</semantics>

</math><img src="./97feeb8799bbd8d617d164ca640abe67ca9fa22b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.062ex; height:2.843ex;" alt="{\displaystyle {\hat {g}}_{N}(x)}" loading="lazy"> has asymptotically normal distribution, i.e., for large <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {g}}_{N}(x)}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {g}}_{N}(x)}</annotation>

</semantics>

</math><img src="./97feeb8799bbd8d617d164ca640abe67ca9fa22b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.062ex; height:2.843ex;" alt="{\displaystyle {\hat {g}}_{N}(x)}" loading="lazy"> has approximately normal distribution with mean <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math><img src="./c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy"> and variance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{N}}\sigma ^{2}(x)}">

<mfrac>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{N}}\sigma ^{2}(x)}</annotation>

</semantics>

</math><img src="./4b28b81ec7b90f324d949635de8f2b050fdf7855.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:8.423ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{N}}\sigma ^{2}(x)}" loading="lazy">. This leads to the following (approximate) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 100(1-\alpha )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 100(1-\alpha )}</annotation>

</semantics>

</math><img src="./87c4072c4da8f027af6c6bf459b80685aa5023de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.787ex; height:2.843ex;" alt="{\displaystyle 100(1-\alpha )}" loading="lazy">% confidence interval for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy">:

<mrow>

<mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<mfrac>

<mrow>

<mover>

</mover>

</mrow>

</mrow>

<msqrt>

</msqrt>

</mfrac>

</mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<mfrac>

<mrow>

<mover>

</mover>

</mrow>

</mrow>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left[{\hat {g}}_{N}(x)-z_{\alpha /2}{\frac {{\hat {\sigma }}(x)}{\sqrt {N}}},{\hat {g}}_{N}(x)+z_{\alpha /2}{\frac {{\hat {\sigma }}(x)}{\sqrt {N}}}\right]}</annotation>

</semantics>

</math><img src="./d8143acc88a78ea0cf121b6ffca33de816eaff11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:39.922ex; height:6.676ex;" alt="{\displaystyle \left[{\hat {g}}_{N}(x)-z_{\alpha /2}{\frac {{\hat {\sigma }}(x)}{\sqrt {N}}},{\hat {g}}_{N}(x)+z_{\alpha /2}{\frac {{\hat {\sigma }}(x)}{\sqrt {N}}}\right]}" loading="lazy"></div>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{\alpha /2}:=\Phi ^{-1}(1-\alpha /2)}">

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{\alpha /2}:=\Phi ^{-1}(1-\alpha /2)}</annotation>

</semantics>

</math><img src="./50f48cbc800f5acd8b0c5dcf0144bd373a358ed2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:21.39ex; height:3.509ex;" alt="{\displaystyle z_{\alpha /2}:=\Phi ^{-1}(1-\alpha /2)}" loading="lazy"> (here <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Phi (\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Phi (\cdot )}</annotation>

</semantics>

</math><img src="./ea6828ad9b892ab12a757eca4bca914d606f6eca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.134ex; height:2.843ex;" alt="{\displaystyle \Phi (\cdot )}" loading="lazy"> denotes the cdf of the standard normal distribution) and

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msup>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {\sigma }}^{2}(x):={\frac {1}{N-1}}\sum _{j=1}^{N}\left[Q(x,\xi ^{j})-{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})\right]^{2}}</annotation>

</semantics>

</math><img src="./2bf6be623be9a7f985827a018cfc97291dfc2e14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:49.843ex; height:8.176ex;" alt="{\displaystyle {\hat {\sigma }}^{2}(x):={\frac {1}{N-1}}\sum _{j=1}^{N}\left[Q(x,\xi ^{j})-{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})\right]^{2}}" loading="lazy"></div>

is the sample variance estimate of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma ^{2}(x)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma ^{2}(x)}</annotation>

</semantics>

</math><img src="./563e81ed7c5ede55b3d8844ea9bc881ec7ad0aa1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.524ex; height:3.176ex;" alt="{\displaystyle \sigma ^{2}(x)}" loading="lazy">. That is, the error of estimation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math><img src="./c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy"> is (stochastically) of order <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\sqrt {N}})}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {N}})}</annotation>

</semantics>

</math><img src="./6a8566840a0a5d4480a0b8ed63d0717c3a89ec9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.582ex; height:3.176ex;" alt="{\displaystyle O({\sqrt {N}})}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Applications_and_examples">Applications and examples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Biological_applications">Biological applications</h3></div>

<a href="Stochastic_dynamic_programming" title="Stochastic dynamic programming">Stochastic dynamic programming</a> is frequently used to model <a href="Ethology" title="Ethology">animal behaviour</a> in such fields as <a href="Behavioural_ecology" class="mw-redirect" title="Behavioural ecology">behavioural ecology</a>.<a href="#cite_note-8">[8]</a><a href="#cite_note-9">[9]</a> Empirical tests of models of <a href="Optimal_foraging_theory" title="Optimal foraging theory">optimal foraging</a>, <a href="Biological_life_cycle" title="Biological life cycle">life-history</a> transitions such as <a href="Fledge" title="Fledge">fledging in birds</a> and egg laying in <a href="Parasitoid" title="Parasitoid">parasitoid</a> wasps have shown the value of this modelling technique in explaining the evolution of behavioural decision making. These models are typically many-staged, rather than two-staged.

<div class="mw-heading mw-heading3"><h3 id="Economic_applications">Economic applications</h3></div>

<a href="Stochastic_dynamic_programming" title="Stochastic dynamic programming">Stochastic dynamic programming</a> is a useful tool in understanding decision making under uncertainty. The accumulation of capital stock under uncertainty is one example; often it is used by resource economists to analyze <a href="Nicholas_Georgescu-Roegen#Man.27s_economic_struggle_and_the_social_evolution_of_mankind_.28bioeconomics.29" title="Nicholas Georgescu-Roegen">bioeconomic problems</a><a href="#cite_note-10">[10]</a> where the uncertainty enters in such as weather, etc.

<div class="mw-heading mw-heading3"><h3 id="Example:_multistage_portfolio_optimization">Example: multistage portfolio optimization</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Intertemporal_portfolio_choice" title="Intertemporal portfolio choice">Intertemporal portfolio choice</a></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Merton's_portfolio_problem" title="Merton's portfolio problem">Merton's portfolio problem</a></div>

The following is an example from finance of multi-stage stochastic programming.

Suppose that at time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=0}</annotation>

</semantics>

</math><img src="./43469ec032d858feae5aa87029e22eaaf0109e9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.101ex; height:2.176ex;" alt="{\displaystyle t=0}" loading="lazy"> we have initial capital <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W_{0}}</annotation>

</semantics>

</math><img src="./7f541f57fd799ba5137a2e50a1a728dde4306c06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.248ex; height:2.509ex;" alt="{\displaystyle W_{0}}" loading="lazy"> to invest in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> assets. Suppose further that we are allowed to rebalance our portfolio at times <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=1,\dots ,T-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=1,\dots ,T-1}</annotation>

</semantics>

</math><img src="./f817857f9a2d46e40fe2f26714adbac1e789d17e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.918ex; height:2.509ex;" alt="{\displaystyle t=1,\dots ,T-1}" loading="lazy"> but without injecting additional cash into it. At each period <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> we make a decision about redistributing the current wealth <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W_{t}}</annotation>

</semantics>

</math><img src="./50680c5535c83badfa630dba63b583d2eeaa2977.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.02ex; height:2.509ex;" alt="{\displaystyle W_{t}}" loading="lazy"> among the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> assets. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}=(x_{10},\dots ,x_{n0})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0}=(x_{10},\dots ,x_{n0})}</annotation>

</semantics>

</math><img src="./fc7b36b679aa4b3b811d333e42ceb72c2b029ed3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.046ex; height:2.843ex;" alt="{\displaystyle x_{0}=(x_{10},\dots ,x_{n0})}" loading="lazy"> be the initial amounts invested in the n assets. We require that each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i0}}</annotation>

</semantics>

</math><img src="./92b936b313824ef06d94c317308bc63fcdbb028d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.951ex; height:2.009ex;" alt="{\displaystyle x_{i0}}" loading="lazy"> is nonnegative and that the balance equation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{i=1}^{n}x_{i0}=W_{0}}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{n}x_{i0}=W_{0}}</annotation>

</semantics>

</math><img src="./fc928154379dc2cc840496caa518a38e473dde12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:13.04ex; height:6.843ex;" alt="{\displaystyle \sum _{i=1}^{n}x_{i0}=W_{0}}" loading="lazy"> should hold.

Consider the total returns <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{t}=(\xi _{1t},\dots ,\xi _{nt})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{t}=(\xi _{1t},\dots ,\xi _{nt})}</annotation>

</semantics>

</math><img src="./247ce5f6b093374a457a529c71270abb06749739.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.427ex; height:2.843ex;" alt="{\displaystyle \xi _{t}=(\xi _{1t},\dots ,\xi _{nt})}" loading="lazy"> for each period <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=1,\dots ,T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=1,\dots ,T}</annotation>

</semantics>

</math><img src="./fad83717deedfb250b91bbc133f7122dd63ab223.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.915ex; height:2.509ex;" alt="{\displaystyle t=1,\dots ,T}" loading="lazy">. This forms a vector-valued random process <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{1},\dots ,\xi _{T}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{1},\dots ,\xi _{T}}</annotation>

</semantics>

</math><img src="./12feee00af59eba7a05db64ff0b3fb01d508c944.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.659ex; height:2.509ex;" alt="{\displaystyle \xi _{1},\dots ,\xi _{T}}" loading="lazy">. At time period <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=1}</annotation>

</semantics>

</math><img src="./970dea4a5f5ec5355c4cdd62f6396fbc8b1baaa1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.101ex; height:2.176ex;" alt="{\displaystyle t=1}" loading="lazy">, we can rebalance the portfolio by specifying the amounts <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}=(x_{11},\dots ,x_{n1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}=(x_{11},\dots ,x_{n1})}</annotation>

</semantics>

</math><img src="./3c5103b67e94291bea795c7ab5f434ffe1885ee5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.046ex; height:2.843ex;" alt="{\displaystyle x_{1}=(x_{11},\dots ,x_{n1})}" loading="lazy"> invested in the respective assets. At that time the returns in the first period have been realized so it is reasonable to use this information in the rebalancing decision. Thus, the second-stage decisions, at time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=1}</annotation>

</semantics>

</math><img src="./970dea4a5f5ec5355c4cdd62f6396fbc8b1baaa1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.101ex; height:2.176ex;" alt="{\displaystyle t=1}" loading="lazy">, are actually functions of realization of the random vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{1}}</annotation>

</semantics>

</math><img src="./c1693cc144ee14052d3469486163441bec3d8e88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.073ex; height:2.509ex;" alt="{\displaystyle \xi _{1}}" loading="lazy">, i.e., <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}=x_{1}(\xi _{1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}=x_{1}(\xi _{1})}</annotation>

</semantics>

</math><img src="./64fe11133ab067ea2fd2176d3e667d679019b2b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.748ex; height:2.843ex;" alt="{\displaystyle x_{1}=x_{1}(\xi _{1})}" loading="lazy">. Similarly, at time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> the decision <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}=(x_{1t},\dots ,x_{nt})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t}=(x_{1t},\dots ,x_{nt})}</annotation>

</semantics>

</math><img src="./6fa02045b7a0adf297556c9a3a3953756c39184d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.361ex; height:2.843ex;" alt="{\displaystyle x_{t}=(x_{1t},\dots ,x_{nt})}" loading="lazy"> is a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}=x_{t}(\xi _{[t]})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t}=x_{t}(\xi _{[t]})}</annotation>

</semantics>

</math><img src="./1c4c87e8bd03667ddfc859878c222f768760b157.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:11.978ex; height:3.176ex;" alt="{\displaystyle x_{t}=x_{t}(\xi _{[t]})}" loading="lazy"> of the available information given by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{[t]}=(\xi _{1},\dots ,\xi _{t})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{[t]}=(\xi _{1},\dots ,\xi _{t})}</annotation>

</semantics>

</math><img src="./cbec2e91abeb7c2dff6418ab77d4a739f92ccb5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:16.762ex; height:3.176ex;" alt="{\displaystyle \xi _{[t]}=(\xi _{1},\dots ,\xi _{t})}" loading="lazy"> the history of the random process up to time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">. A sequence of functions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}=x_{t}(\xi _{[t]})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{t}=x_{t}(\xi _{[t]})}</annotation>

</semantics>

</math><img src="./1c4c87e8bd03667ddfc859878c222f768760b157.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:11.978ex; height:3.176ex;" alt="{\displaystyle x_{t}=x_{t}(\xi _{[t]})}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=0,\dots ,T-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=0,\dots ,T-1}</annotation>

</semantics>

</math><img src="./2e8c2c6b68b131af8c458653826e076473d398fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.918ex; height:2.509ex;" alt="{\displaystyle t=0,\dots ,T-1}" loading="lazy">, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0}}</annotation>

</semantics>

</math><img src="./86f21d0e31751534cd6584264ecf864a6aa792cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{0}}" loading="lazy"> being constant, defines an implementable policy of the decision process. It is said that such a policy is feasible if it satisfies the model constraints with probability 1, i.e., the nonnegativity constraints <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{it}(\xi _{[t]})\geq 0}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{it}(\xi _{[t]})\geq 0}</annotation>

</semantics>

</math><img src="./1a2f628c30ae0cbeb6617b84e714e2fd9ca62b90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:11.552ex; height:3.176ex;" alt="{\displaystyle x_{it}(\xi _{[t]})\geq 0}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=1,\dots ,n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=1,\dots ,n}</annotation>

</semantics>

</math><img src="./f3f269b2f3b2f87fec0168426652a5ea80b56112.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.636ex; height:2.509ex;" alt="{\displaystyle i=1,\dots ,n}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=0,\dots ,T-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=0,\dots ,T-1}</annotation>

</semantics>

</math><img src="./2e8c2c6b68b131af8c458653826e076473d398fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.918ex; height:2.509ex;" alt="{\displaystyle t=0,\dots ,T-1}" loading="lazy">, and the balance of wealth constraints,

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{n}x_{it}(\xi _{[t]})=W_{t},}</annotation>

</semantics>

</math><img src="./f273b99affc7b38b95f0db5290329905ae724664.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:17.799ex; height:6.843ex;" alt="{\displaystyle \sum _{i=1}^{n}x_{it}(\xi _{[t]})=W_{t},}" loading="lazy"></dd></dl>

where in period <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=1,\dots ,T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=1,\dots ,T}</annotation>

</semantics>

</math><img src="./fad83717deedfb250b91bbc133f7122dd63ab223.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.915ex; height:2.509ex;" alt="{\displaystyle t=1,\dots ,T}" loading="lazy"> the wealth <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W_{t}}</annotation>

</semantics>

</math><img src="./50680c5535c83badfa630dba63b583d2eeaa2977.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.02ex; height:2.509ex;" alt="{\displaystyle W_{t}}" loading="lazy"> is given by

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W_{t}=\sum _{i=1}^{n}\xi _{it}x_{i,t-1}(\xi _{[t-1]}),}</annotation>

</semantics>

</math><img src="./766e52fd0bfcd1c129158bbb0cef9c9a2b043924.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:24.869ex; height:6.843ex;" alt="{\displaystyle W_{t}=\sum _{i=1}^{n}\xi _{it}x_{i,t-1}(\xi _{[t-1]}),}" loading="lazy"></dd></dl>

which depends on the realization of the random process and the decisions up to time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">.

Suppose the objective is to maximize the expected utility of this wealth at the last period, that is, to consider the problem

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max E[U(W_{T})].}</annotation>

</semantics>

</math><img src="./361eb1dabb6fb57c8a84cf434c36129aa8b9c400.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.604ex; height:2.843ex;" alt="{\displaystyle \max E[U(W_{T})].}" loading="lazy"></dd></dl>

This is a multistage stochastic programming problem, where stages are numbered from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=0}</annotation>

</semantics>

</math><img src="./43469ec032d858feae5aa87029e22eaaf0109e9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.101ex; height:2.176ex;" alt="{\displaystyle t=0}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=T-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=T-1}</annotation>

</semantics>

</math><img src="./90e40fa338480c5a814e302079152702b88444da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.577ex; height:2.343ex;" alt="{\displaystyle t=T-1}" loading="lazy">. Optimization is performed over all implementable and feasible policies. To complete the problem description one also needs to define the probability distribution of the random process <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{1},\dots ,\xi _{T}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{1},\dots ,\xi _{T}}</annotation>

</semantics>

</math><img src="./12feee00af59eba7a05db64ff0b3fb01d508c944.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.659ex; height:2.509ex;" alt="{\displaystyle \xi _{1},\dots ,\xi _{T}}" loading="lazy">. This can be done in various ways. For example, one can construct a particular scenario tree defining time evolution of the process. If at every stage the random return of each asset is allowed to have two continuations, independent of other assets, then the total number of scenarios is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{nT}.}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{nT}.}</annotation>

</semantics>

</math><img src="./2e41133532c621d7094b05be53c7c4dc7de2ea32.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.185ex; height:2.676ex;" alt="{\displaystyle 2^{nT}.}" loading="lazy">

In order to write <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> equations, consider the above multistage problem backward in time. At the last stage <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=T-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=T-1}</annotation>

</semantics>

</math><img src="./90e40fa338480c5a814e302079152702b88444da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.577ex; height:2.343ex;" alt="{\displaystyle t=T-1}" loading="lazy">, a realization <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{[T-1]}=(\xi _{1},\dots ,\xi _{T-1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{[T-1]}=(\xi _{1},\dots ,\xi _{T-1})}</annotation>

</semantics>

</math><img src="./9472da7b1985654e2ad2a1aa942251bfe031dec9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:22.09ex; height:3.176ex;" alt="{\displaystyle \xi _{[T-1]}=(\xi _{1},\dots ,\xi _{T-1})}" loading="lazy"> of the random process is known and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{T-2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{T-2}}</annotation>

</semantics>

</math><img src="./f5b3e06819e66977c224fd2d2a30ecb5ee079c40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.819ex; height:2.009ex;" alt="{\displaystyle x_{T-2}}" loading="lazy"> has been chosen. Therefore, one needs to solve the following problem

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lrclr}\max \limits _{x_{T-1}}&E[U(W_{T})|\xi _{[T-1]}]&\\{\text{subject to}}&W_{T}&=&\sum _{i=1}^{n}\xi _{iT}x_{i,T-1}\\&\sum _{i=1}^{n}x_{i,T-1}&=&W_{T-1}\\&x_{T-1}&\geq &0\end{array}}}</annotation>

</semantics>

</math><img src="./4aff6e1cb7b24da4b7bee1482954018e2f129836.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.838ex; width:50.232ex; height:14.843ex;" alt="{\displaystyle {\begin{array}{lrclr}\max \limits _{x_{T-1}}&E[U(W_{T})|\xi _{[T-1]}]&\\{\text{subject to}}&W_{T}&=&\sum _{i=1}^{n}\xi _{iT}x_{i,T-1}\\&\sum _{i=1}^{n}x_{i,T-1}&=&W_{T-1}\\&x_{T-1}&\geq &0\end{array}}}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E[U(W_{T})|\xi _{[T-1]}]}">

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E[U(W_{T})|\xi _{[T-1]}]}</annotation>

</semantics>

</math><img src="./c9b3328b09ec5c8b5b9d6ef577852f05e28d1a94.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:16.314ex; height:3.176ex;" alt="{\displaystyle E[U(W_{T})|\xi _{[T-1]}]}" loading="lazy"> denotes the conditional expectation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U(W_{T})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U(W_{T})}</annotation>

</semantics>

</math><img src="./a385b9630ee1fb1106c608131ace38160f78e0b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.175ex; height:2.843ex;" alt="{\displaystyle U(W_{T})}" loading="lazy"> given <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{[T-1]}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{[T-1]}}</annotation>

</semantics>

</math><img src="./973805509f7259ed072bbe78e8a29b09f887cff2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:5.423ex; height:3.009ex;" alt="{\displaystyle \xi _{[T-1]}}" loading="lazy">. The optimal value of the above problem depends on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W_{T-1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W_{T-1}}</annotation>

</semantics>

</math><img src="./9d42ea872bd2fb0c0284c610c40e576af4508fe5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.683ex; height:2.509ex;" alt="{\displaystyle W_{T-1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{[T-1]}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{[T-1]}}</annotation>

</semantics>

</math><img src="./973805509f7259ed072bbe78e8a29b09f887cff2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:5.423ex; height:3.009ex;" alt="{\displaystyle \xi _{[T-1]}}" loading="lazy"> and is denoted <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{T-1}(W_{T-1},\xi _{[T-1]})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{T-1}(W_{T-1},\xi _{[T-1]})}</annotation>

</semantics>

</math><img src="./bb7df5a0d50efd9c8aaca2842518fc0a1564f9a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:19.278ex; height:3.176ex;" alt="{\displaystyle Q_{T-1}(W_{T-1},\xi _{[T-1]})}" loading="lazy">.

Similarly, at stages <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=T-2,\dots ,1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=T-2,\dots ,1}</annotation>

</semantics>

</math><img src="./9b47058476b6832002d988ebf064e5644dad9d27.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.918ex; height:2.509ex;" alt="{\displaystyle t=T-2,\dots ,1}" loading="lazy">, one should solve the problem

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lrclr}\max \limits _{x_{t}}&E[Q_{t+1}(W_{t+1},\xi _{[t+1]})|\xi _{[t]}]&\\{\text{subject to}}&W_{t+1}&=&\sum _{i=1}^{n}\xi _{i,t+1}x_{i,t}\\&\sum _{i=1}^{n}x_{i,t}&=&W_{t}\\&x_{t}&\geq &0\end{array}}}</annotation>

</semantics>

</math><img src="./00c8656a01a165dbeaa35dd136f739edb20e4cec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.671ex; width:57.312ex; height:14.509ex;" alt="{\displaystyle {\begin{array}{lrclr}\max \limits _{x_{t}}&E[Q_{t+1}(W_{t+1},\xi _{[t+1]})|\xi _{[t]}]&\\{\text{subject to}}&W_{t+1}&=&\sum _{i=1}^{n}\xi _{i,t+1}x_{i,t}\\&\sum _{i=1}^{n}x_{i,t}&=&W_{t}\\&x_{t}&\geq &0\end{array}}}" loading="lazy"></dd></dl>

whose optimal value is denoted by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{t}(W_{t},\xi _{[t]})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{t}(W_{t},\xi _{[t]})}</annotation>

</semantics>

</math><img src="./b9b9ff8951ab2abc4d648f0b4492d2e8f56121e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:11.286ex; height:3.176ex;" alt="{\displaystyle Q_{t}(W_{t},\xi _{[t]})}" loading="lazy">. Finally, at stage <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=0}</annotation>

</semantics>

</math><img src="./43469ec032d858feae5aa87029e22eaaf0109e9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.101ex; height:2.176ex;" alt="{\displaystyle t=0}" loading="lazy">, one solves the problem

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lrclr}\max \limits _{x_{0}}&E[Q_{1}(W_{1},\xi _{[1]})]&\\{\text{subject to}}&W_{1}&=&\sum _{i=1}^{n}\xi _{i,1}x_{i0}\\&\sum _{i=1}^{n}x_{i0}&=&W_{0}\\&x_{0}&\geq &0\end{array}}}</annotation>

</semantics>

</math><img src="./3e4040e2ebece795d1d8e32ecec1f64e9e76fab1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.671ex; width:46.188ex; height:14.509ex;" alt="{\displaystyle {\begin{array}{lrclr}\max \limits _{x_{0}}&E[Q_{1}(W_{1},\xi _{[1]})]&\\{\text{subject to}}&W_{1}&=&\sum _{i=1}^{n}\xi _{i,1}x_{i0}\\&\sum _{i=1}^{n}x_{i0}&=&W_{0}\\&x_{0}&\geq &0\end{array}}}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading4"><h4 id="Stagewise_independent_random_process">Stagewise independent random process</h4></div>

For a general distribution of the process <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{t}}</annotation>

</semantics>

</math><img src="./0aa51101d48df4a6bb1e0b282ff03b834c82a7c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.844ex; height:2.509ex;" alt="{\displaystyle \xi _{t}}" loading="lazy">, it may be hard to solve these dynamic programming equations. The situation simplifies dramatically if the process <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{t}}</annotation>

</semantics>

</math><img src="./0aa51101d48df4a6bb1e0b282ff03b834c82a7c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.844ex; height:2.509ex;" alt="{\displaystyle \xi _{t}}" loading="lazy"> is stagewise independent, i.e., <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{t}}</annotation>

</semantics>

</math><img src="./0aa51101d48df4a6bb1e0b282ff03b834c82a7c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.844ex; height:2.509ex;" alt="{\displaystyle \xi _{t}}" loading="lazy"> is (stochastically) independent of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{1},\dots ,\xi _{t-1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{1},\dots ,\xi _{t-1}}</annotation>

</semantics>

</math><img src="./e86a897c7174e6dbb33def0f5b30f4b229526faf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.196ex; height:2.509ex;" alt="{\displaystyle \xi _{1},\dots ,\xi _{t-1}}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=2,\dots ,T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=2,\dots ,T}</annotation>

</semantics>

</math><img src="./a4b970425ae5d7792ae83f5849a97eb8681a2960.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.915ex; height:2.509ex;" alt="{\displaystyle t=2,\dots ,T}" loading="lazy">. In this case, the corresponding conditional expectations become unconditional expectations, and the function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{t}(W_{t})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{t}(W_{t})}</annotation>

</semantics>

</math><img src="./3ac5ead33260912e6d144e7d4e166d680ee1f2e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.493ex; height:2.843ex;" alt="{\displaystyle Q_{t}(W_{t})}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=1,\dots ,T-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=1,\dots ,T-1}</annotation>

</semantics>

</math><img src="./f817857f9a2d46e40fe2f26714adbac1e789d17e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.918ex; height:2.509ex;" alt="{\displaystyle t=1,\dots ,T-1}" loading="lazy"> does not depend on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{[t]}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{[t]}}</annotation>

</semantics>

</math><img src="./ae8e25ef1d2db3fd3d4f5d8977b4d94bfbcdfe50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:2.759ex; height:3.009ex;" alt="{\displaystyle \xi _{[t]}}" loading="lazy">. That is, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{T-1}(W_{T-1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{T-1}(W_{T-1})}</annotation>

</semantics>

</math><img src="./bff01bb8e8c3000dd795b98721214c77565eb35b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.821ex; height:2.843ex;" alt="{\displaystyle Q_{T-1}(W_{T-1})}" loading="lazy"> is the optimal value of the problem

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lrclr}\max \limits _{x_{T-1}}&E[U(W_{T})]&\\{\text{subject to}}&W_{T}&=&\sum _{i=1}^{n}\xi _{iT}x_{i,T-1}\\&\sum _{i=1}^{n}x_{i,T-1}&=&W_{T-1}\\&x_{T-1}&\geq &0\end{array}}}</annotation>

</semantics>

</math><img src="./cb205a5bb173c2ad39e924817211d59bacdc9ac1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.838ex; width:45.504ex; height:14.843ex;" alt="{\displaystyle {\begin{array}{lrclr}\max \limits _{x_{T-1}}&E[U(W_{T})]&\\{\text{subject to}}&W_{T}&=&\sum _{i=1}^{n}\xi _{iT}x_{i,T-1}\\&\sum _{i=1}^{n}x_{i,T-1}&=&W_{T-1}\\&x_{T-1}&\geq &0\end{array}}}" loading="lazy"></dd></dl>

and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{t}(W_{t})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{t}(W_{t})}</annotation>

</semantics>

</math><img src="./3ac5ead33260912e6d144e7d4e166d680ee1f2e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.493ex; height:2.843ex;" alt="{\displaystyle Q_{t}(W_{t})}" loading="lazy"> is the optimal value of

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lrclr}\max \limits _{x_{t}}&E[Q_{t+1}(W_{t+1})]&\\{\text{subject to}}&W_{t+1}&=&\sum _{i=1}^{n}\xi _{i,t+1}x_{i,t}\\&\sum _{i=1}^{n}x_{i,t}&=&W_{t}\\&x_{t}&\geq &0\end{array}}}</annotation>

</semantics>

</math><img src="./183777e5365e288ed829121af98dda49d9fda57f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.671ex; width:48.013ex; height:14.509ex;" alt="{\displaystyle {\begin{array}{lrclr}\max \limits _{x_{t}}&E[Q_{t+1}(W_{t+1})]&\\{\text{subject to}}&W_{t+1}&=&\sum _{i=1}^{n}\xi _{i,t+1}x_{i,t}\\&\sum _{i=1}^{n}x_{i,t}&=&W_{t}\\&x_{t}&\geq &0\end{array}}}" loading="lazy"></dd></dl>

for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=T-2,\dots ,1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=T-2,\dots ,1}</annotation>

</semantics>

</math><img src="./9b47058476b6832002d988ebf064e5644dad9d27.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.918ex; height:2.509ex;" alt="{\displaystyle t=T-2,\dots ,1}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Software_tools">Software tools</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Modelling_languages">Modelling languages</h3></div>

All discrete stochastic programming problems can be represented with any <a href="Algebraic_modeling_language" title="Algebraic modeling language">algebraic modeling language</a>, manually implementing explicit or implicit non-anticipativity to make sure the resulting model respects the structure of the information made available at each stage.

An instance of an SP problem generated by a general modelling language tends to grow quite large (linearly in the number of scenarios), and its matrix loses the structure that is intrinsic to this class of problems, which could otherwise be exploited at solution time by specific decomposition algorithms.

Extensions to modelling languages specifically designed for SP are starting to appear, see:

<ul><li><a href="AIMMS" title="AIMMS">AIMMS</a> – supports the definition of SP problems</li>

<li><a href="Extended_Mathematical_Programming_(EMP)" class="mw-redirect" title="Extended Mathematical Programming (EMP)">EMP SP</a> (Extended Mathematical Programming for Stochastic Programming) – a module of <a href="General_Algebraic_Modeling_System" class="mw-redirect" title="General Algebraic Modeling System">GAMS</a> created to facilitate stochastic programming (includes keywords for parametric distributions, chance constraints and risk measures such as <a href="Value_at_risk" title="Value at risk">Value at risk</a> and <a href="Expected_shortfall" title="Expected shortfall">Expected shortfall</a>).</li>

<li><a href="SAMPL" title="SAMPL">SAMPL</a> – a set of extensions to <a href="AMPL" title="AMPL">AMPL</a> specifically designed to express stochastic programs (includes syntax for chance constraints, integrated chance constraints and <a href="Robust_optimization" title="Robust optimization">robust optimization</a> problems)</li></ul>

They both can generate SMPS instance level format, which conveys in a non-redundant form the structure of the problem to the solver.

<ul><li><a href="Chance-constrained_portfolio_selection" title="Chance-constrained portfolio selection">Chance-constrained portfolio selection</a></li>

<li><a href="Correlation_gap" title="Correlation gap">Correlation gap</a></li>

<li><a href="Extended_Mathematical_Programming_(EMP)" class="mw-redirect" title="Extended Mathematical Programming (EMP)">EMP for Stochastic Programming</a></li>

<li><a href="Entropic_value_at_risk" title="Entropic value at risk">Entropic value at risk</a></li>

<li><a href="FortSP" title="FortSP">FortSP</a></li>

<li><a href="SAMPL" title="SAMPL">SAMPL algebraic modeling language</a></li>

<li><a href="Scenario_optimization" title="Scenario optimization">Scenario optimization</a></li>

<li><a href="Stochastic_optimization" title="Stochastic optimization">Stochastic optimization</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFShapiroDentchevaRuszczyński2009" class="citation book cs1">Shapiro, Alexander; <a href="Darinka_Dentcheva" title="Darinka Dentcheva">Dentcheva, Darinka</a>; <a href="Andrzej_Piotr_Ruszczy%C5%84ski" title="Andrzej Piotr Ruszczyński">Ruszczyński, Andrzej</a> (2009). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20200324131907/https://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/SPbook.pdf">Lectures on stochastic programming: Modeling and theory</a> (PDF). MPS/SIAM Series on Optimization. Vol. 9. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). pp. xvi+436. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89871-687-0</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2562798">2562798</a>. Archived from <a rel="nofollow" class="external text" href="http://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/SPbook.pdf">the original</a> (PDF) on 2020-03-24. Retrieved 2010-09-22.</cite> <code class="cs1-code">{{cite book}}</code>: Unknown parameter <code class="cs1-code">|agency=</code> ignored (help)

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFBirgeLouveaux2011" class="citation book cs1">Birge, John R.; Louveaux, François (2011). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/978-1-4614-0237-4">Introduction to Stochastic Programming</a>. Springer Series in Operations Research and Financial Engineering. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4614-0237-4">10.1007/978-1-4614-0237-4</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4614-0236-7</bdi>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1431-8598">1431-8598</a>.</cite>

</li>

Stein W. Wallace and William T. Ziemba (eds.). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=KAI0jsuyDPsC&q=%22Applications+of+Stochastic+Programming%22">Applications of Stochastic Programming</a>. MPS-SIAM Book Series on Optimization 5, 2005.

</li>

Applications of stochastic programming are described at the following website, <a rel="nofollow" class="external text" href="http://stoprog.org">Stochastic Programming Community</a>.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFShapiroPhilpott" class="citation book cs1">Shapiro, Alexander; Philpott, Andy. <a rel="nofollow" class="external text" href="http://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/TutorialSP.pdf">A tutorial on Stochastic Programming</a> (PDF).</cite>

</li>

<li id="cite_note-neos-6"><a href="#cite_ref-neos_6-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.neos-server.org/neos/">"NEOS Server for Optimization"</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFRuszczyńskiShapiro2003" class="citation book cs1"><a href="Andrzej_Piotr_Ruszczy%C5%84ski" title="Andrzej Piotr Ruszczyński">Ruszczyński, Andrzej</a>; Shapiro, Alexander (2003). Stochastic Programming. Handbooks in Operations Research and Management Science. Vol. 10. Philadelphia: <a href="Elsevier" title="Elsevier">Elsevier</a>. p. 700. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0444508546</bdi>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> Mangel, M. & Clark, C. W. 1988. Dynamic modeling in behavioral ecology. Princeton University Press <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-691-08506-4</bdi>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> Houston, A. I & McNamara, J. M. 1999. Models of adaptive behaviour: an approach based on state. Cambridge University Press <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-521-65539-0</bdi>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> Howitt, R., Msangi, S., Reynaud, A and K. Knapp. 2002. <a rel="nofollow" class="external text" href="http://www.agecon.ucdavis.edu/aredepart/facultydocs/Howitt/Polyapprox3a.pdf">"Using Polynomial Approximations to Solve Stochastic Dynamic Programming Problems: or A "Betty Crocker " Approach to SDP."</a> University of California, Davis, Department of Agricultural and Resource Economics Working Paper.

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li>John R. Birge and François V. Louveaux. <a rel="nofollow" class="external text" href="https://books.google.com/books?id=Vp0Bp8kjPxUC&dq=%22Introduction+to+Stochastic+Programming%22&pg=PR1">Introduction to Stochastic Programming</a>. Springer Verlag, New York, 1997.</li>

<li><cite id="CITEREFKallWallace1994" class="citation book cs1">Kall, Peter; Wallace, Stein W. (1994). <a rel="nofollow" class="external text" href="http://stoprog.org/index.html?introductions.html">Stochastic programming</a>. Wiley-Interscience Series in Systems and Optimization. Chichester: John Wiley & Sons, Ltd. pp. xii+307. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-471-95158-7</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1315300">1315300</a>.</cite></li>

<li>G. Ch. Pflug: <a rel="nofollow" class="external text" href="https://books.google.com/books?id=XJXhBwAAQBAJ&q=%22Stochastic+programming%22&pg=PR13">Optimization of Stochastic Models. The Interface between Simulation and Optimization</a>. Kluwer, Dordrecht, 1996.</li>

<li><a href="Andr%C3%A1s_Pr%C3%A9kopa" title="András Prékopa">András Prékopa</a>. Stochastic Programming. Kluwer Academic Publishers, Dordrecht, 1995.</li>

<li><a href="Andrzej_Piotr_Ruszczy%C5%84ski" title="Andrzej Piotr Ruszczyński">Andrzej Ruszczynski</a> and Alexander Shapiro (eds.) (2003) Stochastic Programming. Handbooks in Operations Research and Management Science, Vol. 10, Elsevier.</li>

<li><cite id="CITEREFShapiroDentchevaRuszczyński2009" class="citation book cs1">Shapiro, Alexander; <a href="Darinka_Dentcheva" title="Darinka Dentcheva">Dentcheva, Darinka</a>; <a href="Andrzej_Piotr_Ruszczy%C5%84ski" title="Andrzej Piotr Ruszczyński">Ruszczyński, Andrzej</a> (2009). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20200324131907/https://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/SPbook.pdf">Lectures on stochastic programming: Modeling and theory</a> (PDF). MPS/SIAM Series on Optimization. Vol. 9. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). pp. xvi+436. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89871-687-0</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2562798">2562798</a>. Archived from <a rel="nofollow" class="external text" href="http://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/SPbook.pdf">the original</a> (PDF) on 2020-03-24. Retrieved 2010-09-22.</cite> <code class="cs1-code">{{cite book}}</code>: Unknown parameter <code class="cs1-code">|agency=</code> ignored (help)</li>

<li>Stein W. Wallace and William T. Ziemba (eds.) (2005) Applications of Stochastic Programming. MPS-SIAM Book Series on Optimization 5</li>

<li><cite id="CITEREFKingWallace2012" class="citation book cs1">King, Alan J.; Wallace, Stein W. (2012). <a rel="nofollow" class="external text" href="https://www.springer.com/mathematics/probability/book/978-0-387-87816-4">Modeling with Stochastic Programming</a>. Springer Series in Operations Research and Financial Engineering. New York: Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-87816-4</bdi>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://stoprog.org">Stochastic Programming Community Home Page</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Major_subfields_of_optimization78" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Major_subfields_of_optimization78" style="font-size:114%;margin:0 4em"><a href="Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)">Major subfields of optimization</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Convex_programming" class="mw-redirect" title="Convex programming">Convex programming</a></li>

<li><a href="Fractional_programming" title="Fractional programming">Fractional programming</a></li>

<li><a href="Integer_programming" title="Integer programming">Integer programming</a></li>

<li><a href="Quadratic_programming" title="Quadratic programming">Quadratic programming</a></li>

<li><a href="Nonlinear_programming" title="Nonlinear programming">Nonlinear programming</a></li>

<li><a href="Robust_optimization" title="Robust optimization">Robust optimization</a></li>

<li><a href="Combinatorial_optimization" title="Combinatorial optimization">Combinatorial optimization</a></li>

<li><a href="Infinite-dimensional_optimization" title="Infinite-dimensional optimization">Infinite-dimensional optimization</a></li>

<li><a href="Metaheuristic" title="Metaheuristic">Metaheuristics</a></li>

<li><a href="Constraint_satisfaction" title="Constraint satisfaction">Constraint satisfaction</a></li>

<li><a href="Multiobjective_optimization" class="mw-redirect" title="Multiobjective optimization">Multiobjective optimization</a></li>

<li><a href="Simulated_annealing" title="Simulated annealing">Simulated annealing</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-27" href="https://en.wikipedia.org/wiki/?title=Stochastic_programming&oldid=1297667306">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>